package com.fw.leetcode.stack;

import com.fw.leetcode.LeetCode;

import java.util.Arrays;

/**
 * 321. Create Maximum Number
 *
 * You are given two integer arrays nums1 and nums2 of lengths m and n respectively.
 * nums1 and nums2 represent the digits of two numbers. You are also given an integer k.
 *
 * Create the maximum number of length k <= m + n from digits of the two numbers.
 * The relative order of the digits from the same array must be preserved.
 *
 * Return an array of the k digits representing the answer.
 *
 * Example 1:
 *  Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
 *  Output: [9,8,6,5,3]
 *
 * Example 2:
 *  Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
 *  Output: [6,7,6,0,4]
 *
 * Example 3:
 *  Input: nums1 = [3,9], nums2 = [8,9], k = 3
 *  Output: [9,8,9]
 *
 * Constraints:
 *  m == nums1.length
 *  n == nums2.length
 *  1 <= m, n <= 500
 *  0 <= nums1[i], nums2[i] <= 9
 *  1 <= k <= m + n
 */
public class Num_0321 implements LeetCode {
    private interface Solution {
        int[] maxNumber(int[] nums1, int[] nums2, int k);

        default void assertEquals(int[] nums1, int[] nums2, int k, int[] expected) {
            if (!Arrays.equals(maxNumber(nums1, nums2, k), expected)) {
                maxNumber(nums1, nums2, k);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public int[] maxNumber(int[] nums1, int[] nums2, int k) { // 枚举 + 单调栈 + 合并：时O(k(m+n+k^2)) 空O(k)
            /*
             * 拼接最大数（长度k）
             * - 观察到数字大小的起伏状态
             *
             *  0 1 2 3     0 1 2 3 4 5
             * [3,4,6,5] + [9,1,2,5,8,3] k=5 => [9,8,6,5,3]
             *
             * 暴力：分别枚举两侧子序列，后合并，找最大组合
             * 1.暴力枚举 k 的拆分组合 (left, right)：(0,k),(1,k-1)..(k,0) => 需注意边界防止数组下标越界
             * 2.单调栈求子序列最大值：依次求 nums1 的 left 个子序列最大值，求 nums2 的 right 个子序列最大值
             * 3.两个子序列合并
             * 4.求最大合并值
             */
            int n1 = nums1.length;
            int n2 = nums2.length;
            int[] maxMergedNums = new int[k]; // 最大合并序列，长度 k，初始化0
            // 依次遍历不同数量组合（拆分k）
            // k > n1 时，left 最大只能取 n1，否则越界
            // k - left = right 必须 <= n2，否则越界
            for (int left = Math.max(0, k - n2); left <= Math.min(n1, k); left++) {
                int[] nums1Max = subSeqMax(nums1, left); // 求 nums1 子序列
                int[] nums2Max = subSeqMax(nums2, k - left); // 求 nums2 子序列
                int[] mergedNums = merge(nums1Max, nums2Max); // 合并序列，长度 k
                // 与之前最大值比较，若更大则替换
                if (compare(mergedNums, maxMergedNums) > 0) {
                    System.arraycopy(mergedNums, 0, maxMergedNums, 0, k);
                }
            }
            return maxMergedNums;
        }

        private int[] subSeqMax(int[] nums, int k) {
            /*
             * 寻找 nums[](k) 中 k 子序列的最大值组合：单调栈
             *
             * [5,4,3,2,1] k = 3 => [5,4,3]
             * [5,4,3,8,1] k = 3 => [5,8,1]
             *
             * 替换栈顶（将栈顶出栈）条件：
             * 1）栈顶非空
             * 2）大于栈顶数字
             * 3）nums 剩余位数能满足 k 个需求
             *   假设栈出栈栈顶丢弃，则栈中剩余 top 个
             *   nums 中剩余 nums.length - i
             *   需满足：top + nums.length - i >= k
             */
            if (k == 0) return new int[0];
            if (nums.length == k) return nums;
            int[] stack = new int[k]; // 单调栈
            int top = -1; // 栈顶指针
            for (int i = 0; i < nums.length; i++) {
                while (top > -1 && nums[i] > stack[top] && top + nums.length - i >= k) {
                    top--;
                }
                if (top < k-1) {
                    // 入栈
                    stack[++top] = nums[i];
                }
            }
            return stack;
        }

        private int[] merge(int[] nums1, int[] nums2) {
            /*
             * 合并两个子序列
             *
             * nums1=[6,7] nums2=[6,0,4]
             * 两个相等时，看下一位
             * 如：nums1[0] == nums2[0]，nums1[1] > nums2[1] => nums[0] 优先合入
             * 即：6 == 6 时，7 > 0，优先合入 nums1 中的 6
             *
             * 特例：遇到边界时为小
             * nums1=[0,5,6] nums2=[0] => [0,5,6,0] 而非 [0,0,5,6]
             */
            int n1 = nums1.length;
            int n2 = nums2.length;
            int[] merged = new int[n1 + n2]; // 长度 k
            int idx0 = 0;
            int idx1 = 0;
            int idx2 = 0;
            while (idx1 < n1 && idx2 < n2) {
                // 比较 nums1[idx1] 和 nums2[idx2] 字典序，相等时将比较下一位
                merged[idx0++] = compare(nums1, idx1, nums2, idx2) > 0 ? nums1[idx1++] : nums2[idx2++];
            }
            while (idx1 < n1) {
                merged[idx0++] = nums1[idx1++];
            }
            while (idx2 < n2) {
                merged[idx0++] = nums2[idx2++];
            }
            return merged;
        }

        private int compare(int[] nums1, int idx1, int[] nums2, int idx2) { // 比较两个字符序列字典序
            while (idx1 < nums1.length && idx2 < nums2.length) {
                if (nums1[idx1] != nums2[idx2]) {
                    return Integer.compare(nums1[idx1], nums2[idx2]);
                }
                idx1++;
                idx2++;
            }
            // 若未在 nums 长度范围内比较出，则可能到达边界，还有剩余元素的较大
            return nums1.length - idx1 - (nums2.length - idx2);
        }

        private int compare(int[] nums1, int[] nums2) { // 比较两个序列大小，相同长度
            return compare(nums1, 0, nums2, 0);
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertEquals(new int[]{3,4,6,5}, new int[]{9,1,2,5,8,3}, 5, new int[]{9,8,6,5,3});
        solution.assertEquals(new int[]{6,7}, new int[]{6,0,4}, 5, new int[]{6,7,6,0,4});
        solution.assertEquals(new int[]{3,9}, new int[]{8,9}, 3, new int[]{9,8,9});
        solution.assertEquals(new int[]{6,3,9,0,5,6}, new int[]{2,2,5,2,1,4,4,5,7,8,9,3,1,6,9,7,0}, 23, new int[]{6,3,9,2,2,5,2,1,4,4,5,7,8,9,3,1,6,9,7,0,5,6,0}); // 边界错误
    }
}
